package acwing._2LanQiao._10Other;
/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._2LanQiao._10Other
 * @File : Q0523.java
 * @Author : WangRuoyu
 * @Date : 2023/3/27 15:28
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q0523 {
    static int t;
    static int k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] words = br.readLine().split(" ");

        t = Integer.parseInt(words[0]);
        k = Integer.parseInt(words[1]);
        int[][] cmodk = new int[2001][2001];

        for (int i = 0; i < 2001; ++i) {
            cmodk[0][i] = 1;
        }

        for (int i = 1; i <= 2000; ++i) {
            for (int j = 1; j <= 2000; ++j) {
                if (i == j) cmodk[i][j] = 1;
                else if (j < i) cmodk[i][j] = -1;
                else {
                    cmodk[i][j] = (cmodk[i - 1][j - 1] + cmodk[i][j - 1]) % k;
                }
            }
        }

        int[][] s = new int[2001][2001];
        for (int i = 1; i <= 2000; ++i) {
            for (int j = 1; j <= 2000; ++j) {
                int x;
                if (cmodk[i][j] == 0) x = 1;
                else x = 0;
                s[i][j] = x + s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];
            }
        }

        for (int i = 0; i < t; ++i) {
            words = br.readLine().split(" ");
            int m = Integer.parseInt(words[0]);
            int n = Integer.parseInt(words[1]);
            System.out.println(s[n][m]);
        }
    }
}

//3 11
//22 1256
//14 889
//10 437